package com.cjm.algorithm.babo;

import com.cjm.algorithm.GeneratorUtils;

/**
 * 1, 从第一个元素开始, 该元素可以认为已经被排序;
 * 2, 取出下一个元素, 在已经排序的元素序列中从后向前扫描;
 * 3, 如果该元素(已排序)大于新元素, 将元素移动到下一位置;
 * 4, 重复步骤3步,直到找到已经排序的元素小于或者等于新元素的位置;
 * 5, 将新元素插入到该位置后;
 * 6, 重复2~5;
 */
public class InsertSort {
    public static void insertSort() {
        System.out.println("插入排序\r\n");
        int[] arr = GeneratorUtils.generator();
        insertSort(arr);
        GeneratorUtils.print(arr);
    }
    public static int[] insertSort(int[] arr) {
        long l = System.currentTimeMillis();
        int length = arr.length;
        for (int i = 1; i < length; i++) {
            // 把一个值给拿出来
            int temp = arr[i];
            // j = i,
            int j = i;
            while (j > 0 && temp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            if (j != i) {
                arr[j] = temp;
            }
        }
        long l1 = System.currentTimeMillis();
        System.err.println("花了" + (l1 - l) + "ms");
        return arr;
    }

    public static void xx(int[] arr) {
        int len = arr.length;
        // 假设第一个元素是有序的
        for (int i = 1;i<len;i++) {
            // 用一个临时变量将走到的这个索引位置的值给保存起来
            int temp = arr[i];
            // 用一个临时变量, 将这个索引给保存起来
            int j = i;
            while (j>0&&temp<arr[j-1]) {
                // j>0 && 这个要比较的值与小一个索引的值 进行比较, 如果位置较小的值大的话, 将这个值,给移动一位
                arr[j] = arr[j - 1];
                j--;
            }
            // 到这里的话, 证明j-1的位置的值是小于temp的, 那么 j的位置 就是tmep应该待的位置
            if (j != i) {
                arr[j] = temp;
            }
        }
    }

    public static void sort(int[] arr) {
        for(int i = 1;i<arr.length;i++) {
            int temp = arr[i];
            int j = i;
            for(;j>0&&arr[j-1]>temp;j--) {
                arr[j] = arr[j-1];
            }
            if (i!=j) {
                arr[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            int[] generator = GeneratorUtils.generator(1000, 0, 1000);
            sort(generator);
            GeneratorUtils.print(generator);
        }
    }
}
